#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int tasks[] = {12,4,6,8,10};
int prior[] = {2,5,1,3,4};

void swap_task(int t[], int p[],int i, int j)
{
    int temp;
    temp=t[i];
    t[i]=t[j];
    t[j]=temp;

    temp=p[i];
    p[i]=p[j];
    p[j]=temp;
}


void qsort_task(int t[], int p[],int left,int right,int inc)
{
    int i,last;
    if(left>=right)
        return ;
    swap_task(t,p,left,(left+right)/2);
    last=left;
    for(i=left+1;i<=right;i++)
        if(inc?(p[i]<p[left]):(p[i]>p[left]))
            swap_task(t,p,++last,i);
    swap_task(t,p,left,last);
    qsort_task(t,p,left,last-1,inc);
    qsort_task(t,p,last+1,right,inc);
}

void print_arr(int v[], int n)
{
    for(int i = 0; i<n;i++)
    {
        printf("%d ",v[i]);
    }
    putchar('\n');
}

int task_finish(int t[],int task_n)
{
    int finish = 1;
    for(int i = 0; i< task_n;i++)
    {
        if(t[i]>0)
        {
            finish = 0;
            break;
        }
        else if(t[i] < 0)
        {
            printf("Error: task %d with negtive time %d\n",i,tasks[i]);
            exit(2);
        }
    }
    return finish;
}
void round_robin(int t[], int task_n, int slice)
{
    int current_time = 0;
    int average_waiting_time = 0;
    int *waiting_time = malloc(task_n);
    int *last_serve_time = malloc(task_n);
    if(waiting_time == NULL || last_serve_time == NULL)
    {
        printf("round_robin: Error at malloc");
        exit(1);
    }
    bzero(waiting_time,task_n);
    bzero(last_serve_time,task_n);
    
    if(task_n <= 0)
    {
        printf("round_robin: Invalid task number %d\n",task_n);
        exit(3);
    }
    if(slice <=0 )
    {
        printf("round_robin: Invalid slice number %d\n",slice);
        exit(3);
    }
    
    while(!task_finish(t,task_n))
    {
        for(int i =0;i<task_n;i++)
        {
            if(t[i] == 0 )
                continue;
            if(slice > t[i])
            {
                printf("[task%d:%d] ",i,t[i]);
                waiting_time[i] += current_time - last_serve_time[i];
                last_serve_time[i] = current_time;
                current_time += t[i];
                t[i] = 0;
            }
            else if(t[i] > 0)
            {
                printf("[task%d:%d] ",i,slice);
                waiting_time[i] += current_time -last_serve_time[i];
                last_serve_time[i] = current_time;
                current_time += slice;
                t[i]-=slice;
            }
            else
            {
                printf("Error task remaining time: %d\n",t[i]);
                exit(3);
            }
        }
    }
    printf("waiting time:\n");

    for(int i = 0; i<task_n;i++)
    {
        printf("[task%d:%d] ",i,waiting_time[i]);
    }
    putchar('\n');
    printf("Average waiting time: ");
    for(int i = 0; i<task_n;i++)
    {
        average_waiting_time += waiting_time[i];
    }
    printf("%.1f\n",(float)average_waiting_time / task_n);

    free(waiting_time);
}

void use_priority(int t[], int p[], int task_n)
{
    int current_time = 0;
    int average_waiting_time = 0;
    int *waiting_time = malloc(task_n);
    if(waiting_time == NULL)
    {
        printf("round_robin: Error at malloc");
        exit(1);
    }
    bzero(waiting_time,task_n);
    if(task_n <= 0)
    {
        printf("round_robin: Invalid task number %d\n",task_n);
        exit(3);
    }
    
    qsort_task(t,p,0,task_n-1,0);
    print_arr(t,task_n);
    print_arr(p,task_n);
    for(int i = 0;i<task_n;i++)
    {
        waiting_time[i] += current_time;
        current_time += t[i];
        t[i] = 0;
    }
    printf("waiting time:\n");

    for(int i = 0; i<task_n;i++)
    {
        printf("[task%d:%d] ",i,waiting_time[i]);
    }
    putchar('\n');
    printf("Average waiting time: ");
    for(int i = 0; i<task_n;i++)
    {
        average_waiting_time += waiting_time[i];
    }
    printf("%.5f\n",(float)average_waiting_time / task_n);

    free(waiting_time);
}

void short_first(int t[], int p[], int task_n)
{
    int current_time = 0;
    int average_waiting_time = 0;
    int *waiting_time = malloc(task_n);
    if(waiting_time == NULL)
    {
        printf("round_robin: Error at malloc");
        exit(1);
    }
    bzero(waiting_time,task_n);
    if(task_n <= 0)
    {
        printf("round_robin: Invalid task number %d\n",task_n);
        exit(3);
    }
    
    qsort_task(p,t,0,task_n-1,1);
    print_arr(t,task_n);
    // print_arr(p,task_n);
    for(int i = 0;i<task_n;i++)
    {
        waiting_time[i] += current_time;
        current_time += t[i];
        t[i] = 0;
    }
    printf("waiting time:\n");

    for(int i = 0; i<task_n;i++)
    {
        printf("[task%d:%d] ",i,waiting_time[i]);
    }
    putchar('\n');
    printf("Average waiting time: ");
    for(int i = 0; i<task_n;i++)
    {
        average_waiting_time += waiting_time[i];
    }
    printf("%.5f\n",(float)average_waiting_time / task_n);

    free(waiting_time);
}



int main()
{
    int task_num = sizeof(tasks)/sizeof(int);
    // printf("%d",task_finish(tasks,task_num));
    // round_robin(tasks,task_num,1);
    use_priority(tasks,prior,task_num);
    // round_robin(tasks,task_num,1000);
    // short_first(tasks,prior,task_num);
    return 0;
}